Certain embodiments of the present invention generally relate to systems and methods for calculating navigation routes based on map databases indicative of overlapping, non-contiguous geographic regions. Certain embodiments of the present invention generally relate to navigation systems and methods that utilize roadway map databases organized in different tiers or levels of a map hierarchy.
Route planning systems are well known in the field of navigational instruments. Route planning systems in general calculate one or more paths through a network of roads between source and destination locations. The path(s) planned by the system may be based on one or more criteria, such as shortest distance, shortest time, user preferences and the like. Several algorithms are known for performing route planning, with such algorithms calculating the route from the source or destination location or from both simultaneously. Conventional planning algorithms operate based on a predefined stored map database, which includes data indicative of a geographic region containing the source and destination locations.
In general, each map database corresponds to a particular geographic region, such as a city, a county, a state, a country, a continent, etc. Each map database contains data indicative of features within the associated geographic region with varied levels of specificity concerning the features. For example, each map database includes data indicative of nodes representing intersections between roadways and data indicative of segments representative of roadway portions extending between nodes. In general, map databases representing smaller geographic regions (e.g. cities) contain more detailed feature information (county roads, city streets, restaurants, and the like), while map databases representing larger geographic regions (e.g. states and countries) contain less detailed feature information (e.g. interstates, state highways, gas stations, hotels, rest stops, and the like). The feature information stored within each map database may include geographic coordinates (i.e. altitude, longitude and latitude) among other things. Each map database is bound by a geographic region perimeter or boundary.
Conventional methods for route planning depend on the capabilities of system resources, such as processor speed and the amount and speed of memory. To reduce the amount of memory needed, route planning or navigation devices typically do not store a detailed map of a large geographic area, such as North America. Instead, the memory for the route planning or navigation device is initially loaded with a detailed map (e.g. a map database containing detailed feature information for a small geographic region) only for a select geographic region, such as a particular city in which the user travels. When the user wishes to chart a path across a particular city, the user enters the source and destination locations in the particular city. The route planning or navigation device uses the detailed map database for the corresponding city map to plan a route between the source and destination locations. Both the source and destination locations are within the boundaries of the detailed map (i.e. within the particular city).
The route planning or navigation device may instead be loaded with a less detailed xe2x80x9cbasexe2x80x9d map (e.g. map database containing general feature information for a large geographic region), such as the United States. When the user wishes to chart a path between cities, across the country, etc., the user first selects or loads the base map and then enters the source and destination locations. The route planning and navigation device accesses and plans a route through the base map. Hence, for long trips, the route planning and navigation device only utilizes the base map and thus is only able to offer limited information regarding the details of a planned route.
Due to memory constraints, the base map database includes less detailed feature information and may lack feature information surrounding the source and destination locations of interest to the user. The user may desire detailed feature information present only in a detailed map database, such as street information for source and destination cities. In general, each map database is stored on a separate CD. The route planning and navigation device typically only accesses a single CD at any given time since the user can only load one CD at a time. Heretofore, the user could only chart routes through one detailed map database or through one base map database at any particular time, namely when the appropriate CD was loaded.
For example, when planning a trip between Kansas City and Denver, the user would load a CD into the route planning device containing only the base map database that would encompass both cities. The user would then enter source and destination coordinates within the base map database. If the user desired detailed street information for Kansas City, for example, directions to Arrowhead Stadium, conventional navigation devices were unable to provide such information while simultaneously providing a route between cities since the street information was only on detailed map databases, while only the base map database could be used to provide routing. Instead, the user was required to remove the CD containing the base map database and load a CD containing a detailed map database for Kansas City. The user then entered a source location, such as along interstate 70 on the west side of town, and a destination location for Arrowhead Stadium. Similarly, if the user desired detailed street information for Denver, the prior CD containing the Kansas City street map must be removed and a separate CD containing a detailed street map for Denver must be loaded. Source and destination locations would again need to be entered by the user for the Denver area. In the foregoing example, conventional navigation devices require the user to load three separate CDs and to perform three separate source and destination data entry procedures.
Presently, cartographic information is charted or mapped by data suppliers as large cartographic data blocks. A single cartographic data block may include detailed maps for multiple adjoining metropolitan areas and/or detailed maps for large geographic areas and the like. A cartographic data block is typically divided by the data supplier, by the manufacturer of the routing devices or by the service provider into smaller map databases having a size more conducive to storage on, or wireless transmission to, a navigation or route planning device. By way of example only, a large block of cartographic data may constitute a detailed map of the metropolitan corridor for the East coast between Washington, DC and Boston. The cartographic data block may be divided into a first map database for the Washington, DC metropolitan area, a second map database for the Baltimore metropolitan area, a third map database for the Philadelphia metropolitan area, and so on. The map databases for Washington, DC and Baltimore may include matching roadway/boundary longitude and latitude coordinates since the map databases were xe2x80x9ccutxe2x80x9d from a common cartographic data block or xe2x80x9cfabricxe2x80x9d. However, each map database would nonetheless be provided as a separate map, such as on a separate CD. Accordingly, users would be required to switch CDs and perform independent routing operations based on discrete, separate map databases.
Today, numerous data suppliers map and chart roadway networks independent of one another. Typically, cartographic data from one supplier does not match cartographic data from a different supplier. Hence, when cartographic data blocks from different suppliers are divided into map databases, the map databases from different suppliers do not match, even though the map databases may be for common or overlapping geographic areas. For example, cartographic data for a map of Washington, DC from one data supplier will include geographic coordinates for the U.S. Capital that may differ (albeit slightly) from geographic coordinates in a second data supplier""s cartographic data for the U.S. Capital. Similarly, the first supplier""s cartographic data for downtown Washington, DC may include coordinates for Highways 50 and 66 that differ (albeit slightly) from coordinates for the same highways in a second supplier""s cartographic data.
Conventional navigation and route planning devices must separately and independently access and operate on individual map databases even if multiple map databases are simultaneously loaded or accessible. The navigation and route planning devices are only able to calculate paths between sources and destinations in a single map database. Conventional route planning devices are unable to plan routes between source and destination locations that are located in different map databases.
A need exists for improved navigation and route planning devices capable of automatically calculating potential paths between a single source location and a single destination location based on any and all available map databases, regardless of whether the map databases 1) are contiguous or non-contiguous with one another, 2) are xe2x80x9ccutxe2x80x9d from common or different cartographic data blocks, or 3) are obtained from the same or different data suppliers. A need further exists for a navigation device capable of accessing multiple map databases to plan a single route.
Certain embodiments of the present invention relate to a method for providing a navigation route between source and destination locations. The method includes providing first and second map databases indicative of roadway networks for geographic regions bounded by region edges. The first and second map databases each contain one of the source and destination locations. The first and second map databases are not contiguous with one another inasmuch as the region edges of the first and second map databases are separate and distinct from one another. The method further includes calculating potential paths through the roadway network of the first map database and identifying a node/edge coordinate at which each potential path intersects a region edge of the first map database. For each potential path, a transition location is identified in the second map database that geographically corresponds to the node/edge coordinate where the associated potential path intersects the region edge of the first map database. The method may further include searching the second map database for roads within a search perimeter surrounding the node/edge coordinate to obtain each transition location. The method continues by calculating potential paths from each transition location through the roadway network of the second map database. After a number of potential paths between the source and destination locations are analyzed, a navigation route is selected.
Optionally, the method may include organizing at least first and second map databases into first and second map tiers based on certain criteria, such as the data supplier of the first and second map databases and/or an amount of detailed feature information held in the map databases concerning corresponding geographic regions. Once the first and second map databases are organized into tiers, the planning method begins performing the first calculating step based on map databases in the first map tier. As potential paths intersect the boundary of the first map database, the planning method performs the obtaining and second calculating steps based on map databases in the second map tier.
Optionally, the first map database may contain a low level detailed map of the geographic region surrounding the source, the second map database may contain a high level base map of the geographic region encompassing both the first map database and a third map database that contains a low level detailed map of the geographic region surrounding the destination location. The first and third map databases may be non-overlapping and non-contiguous, or may be overlapping yet have other characteristics that cause them to be classified in different map tiers. Alternatively, the first map database may represent a detailed map of one metropolitan area and the second map database may represent a base map of a larger geographic region encompassing a portion of the first metropolitan area.
In another embodiment, a method is provided for calculating a navigation route between first and second points based on map databases organized in a map hierarchy. The method involves providing a number of map databases indicative of an equal number of roadway networks for geographic regions, with each map database having map edges. The method includes organizing the map databases into a map hierarchy by assigning at least one map database to a first level of the map hierarchy to define at least one tier-one map database and by assigning at least one map database to a second level of the map hierarchy to define at least one tier-two map database. The method also includes utilizing the tier-one map databases to plan potential paths from one of the first and second points until each potential path intersects the map edge of an outer tier-one map database; and thereafter, automatically continuing planning of each potential path based on the tier-two map databases.
The navigation route calculation method is capable of utilizing a variety of map databases. For example, the map databases may include first and second tier-one map databases that correspond to non-overlapping first and second geographic regions that surround the first and second points, respectively. Optionally, the map databases may include a tier N map database for a geographic region that contains the first point, but not the second point, and a tier N+M map database for a geographic region that contains both the first and second points. As another example, the map databases may include first and second tier N map databases for a geographic region that contains the first and second points, respectively, and a tier N+M map database for a geographic region partially overlapping the geographic regions associated with the first and second map databases, where the geographic region defined by data in the tier N+M map database excludes the first and second points. As yet another example, the map databases may include first and second tier N map databases containing detailed maps of areas surrounding the first and second points, respectively, and a tier N+M map database containing a base map overlapping both of the detailed maps, where the base map includes the first and second points.
The navigation route calculating method transitions from one map database to another, during a route planning search, each time a potential path intersects a boundary of a map database. To effect a transition from a current map database, the method first searches other map databases at the present tier, (e.g., assigned to the same tier as the current map database). The map databases at the present tier are searched for a point in a respective roadway network corresponding to the point at which potential path intersected the boundary of the current map database. If no map database is identified in the present tier, then the search is repeated for map databases at other tiers.
When searching map databases at a common tier, once potential paths intersect the map edge of a first tier-one map database, the calculation method determines whether a second tier-one map database exists that has a map edge that joins the map edge of the first tier-one map database. If no other tier-one map database has a map edge joining the first tier-one map database, then a local search is performed to identify a translation location in a tier-two map database. The local search is based on a location, at which the potential path intersects the map edge of the tier-one map database. The translation location represents a starting point within a tier-two map database from which the route planning operation continues along potential paths.
The calculating method may include identifying, in the tier-one map databases, a tier-one coordinate indicative of a point at which the potential path intersects the map edge and searching a geographic region for at least one of the tier-two map databases for a tier-two coordinate corresponding to the tier-one coordinate. Alternatively, the identifying step may include identifying, in the tier-two map databases, a road having a generally common direction of travel as the potential path at or near the point of intersection of the potential path with the map edge of the tier-one map database.
In an alternative embodiment, a navigation system is provided that includes memory storing map databases indicative of roadway networks in respective geographic regions surrounded by region edges. The map databases include first and second map databases. The geographic regions contain first and second navigation points. The first and second map databases correspond to geographic regions having separate and distinct non-adjacent region edges. The navigation system includes a planner calculating a path between the first and second navigation points based on roadway network information in both of the first and second map databases. The planner switches the search from potential paths defined in the first map database to potential paths defined in the second data each time the planner progresses along a potential path to a point at which the potential path intersects a region edge of the first map database. A display is provided to illustrate the final potential path generated by the planner. The system is operable with a compilation of map databases 1) that are contiguous, 2) that are not contiguous, 3) that overlap one another, 4) that are cut from common or different cartographic data blocks, and 5) that are obtained from different or common sources.
Optionally, the first and second map databases may be non-overlapping and the memory may store or have access to a third map database which at least partially overlaps the first and second map databases. When three map databases are employed in this manner, the navigation system jumps directly from the first map database to the third map database and then directly from the third map database to the second map database during the route planning operation as potential paths intersect map edges. Alternatively, when the first and second map databases do not overlap one another yet overlap a third map database, the navigation system may perform bi-directional route planning operations from the first and second map databases and jump to the third map database when the potential paths reach the edges of the first and second map databases.
The system may be equipped with a module that organizes the map databases into a mapping hierarchy by assigning the first map database to a first level to define a tier one map database and by assigning the second map database to a second level to define a tier-two map database.
In accordance with another embodiment, a hand-held portable navigation device is provided that includes memory storing map databases indicative of roadway networks and respective geographic regions surrounded by region edges. The map databases include first and second map databases that correspond to geographic regions having separate and distinct non-adjacent region edges. The geographic regions contain the first and second navigation points. The navigation device also includes a processor which calculates a path between the first and second navigation points based on roadway network information in both the first and second map databases. The processor moves, during a path-planning operation, from potential paths based on the first map database to potential paths based on the second map database and vice versa each time the potential path intersects a region edge for a map database. A display is provided to illustrate the final potential path generated by the processor.